package com.leetcode.LC_MED;

public class LC494 {
    int rsNum = 0;

    public int findTargetSumWays(int[] nums, int S) {
        dp(nums, nums.length - 1, S);
        return rsNum;
    }

    private void dp(int[] nums, int num, int S) {
        if (num < 0 && S == 0) {
            rsNum++;
            return;
        } else if (num < 0) {
            return;
        }
        dp(nums, num - 1, S + nums[num]);
        dp(nums, num - 1, S - nums[num]);
    }

    public static void main(String[] args) {
        System.out.println(new LC494().findTargetSumWays(new int[]{1, 1, 1,2}, 3));
    }
}
